Conventionally, Huffman coding is known as one of the most efficient reversible compression techniques in data compression techniques (D. A. Huffman, “A method for the construction of minimum redundancy codes,” Proc. IRE, no. 40, pp. 1098-1101, September 1952).
General Huffman coding first creates a coding table suitable for target data by carefully examining all coding target symbol sequences before performing a compression process, and performs the compression process by using the created coding table again for similar symbol sequences.
However, since this method needs to scan the data twice for performing the compression, online real time compression becomes difficult. Moreover, if there are many types of the coding target symbol sequences and there is a bias in frequencies of occurrence thereof, improvement of a compression ratio may not be expected.
The Huffman coding has, therefore, been classified into two kinds recently: static Huffman coding and dynamic (also referred to as “adaptive”) Huffman coding (D. E. Kunth, “Dynamic Huffman coding,” J. Algorithms, vol. 6, pp. 163-180, 1985).
The static Huffman coding is the most common form of implementation in both software and hardware. In addition, in order to execute a coding process in real time, the static Huffman coding previously examines frequencies of occurrence of data from a large number of pieces of sample data, prepares an existing table created based on a result thereof, and performs the coding.
The dynamic Huffman coding has been developed in order to improve the online compression which has been a challenge in the conventional Huffman coding, and compression suitable for arbitrary symbol sequences without an existing table, which has been a challenge in the static Huffman coding. The dynamic Huffman coding updates a Huffman tree each time a symbol is processed, and performs the coding by using the tree composed at that time point.